package com.cjl.interview150.hash;

import org.junit.jupiter.api.Test;

import java.util.*;

public class HashPractice {
    /**
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> sMap = new HashMap<>();
        HashMap<Character, Character> tMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char x = s.charAt(i);
            char y = t.charAt(i);
            if ((sMap.containsKey(x) && sMap.get(x) != y) || (tMap.containsKey(y) && tMap.get(y) != x)) {
                return false;
            }
            sMap.put(x, y);
            tMap.put(y, x);
        }
        return true;
    }

    /**
     *
     * @param pattern
     * @param s
     * @return
     */
    public boolean wordPattern(String pattern, String s) {
        HashMap<Character, String> c2s = new HashMap<>();
        HashMap<String, Character> s2c = new HashMap<>();
        String[] arr = s.split(" ");
        if (pattern.length() != arr.length) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String str = arr[i];
            if ((c2s.containsKey(c) && !c2s.get(c).equals(str)) || (s2c.containsKey(str) && s2c.get(str) != c)) {
                return false;
            }
            c2s.put(c, str);
            s2c.put(str, c);
        }
        return true;
    }

    /**
     * 49. 字母异位词分组
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        // 互为异位的词排序后一定相等
        HashMap<String, List<String>> map = new HashMap<>();
        // 对每一个字符串排序并统计
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            // 加入异位字符
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    /**
     * 219. 存在重复元素 II
     * 维护一个哈希表，里面始终最多包含 k 个元素，当出现重复值时则说明在 k 距离内存在重复元素
     * 每次遍历一个元素则将其加入哈希表中，如果哈希表的大小大于 k，则移除最前面的数字
     * 时间复杂度：O(n)O(n)O(n)，nnn 为数组长度
     * @param nums
     * @param k
     * @return
     */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (set.contains(num)) {
                return true;
            }
            set.add(num);
            // 当距离大于k则删除开头的元素，保持k的距离
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        // 如果循环结束还没返回ture表示没有k距离内没有重复元素
        return false;
    }

    /**
     * 128. 最长连续序列
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        // 使用set去重
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int longestLength = 0;
        for (Integer num : set) {
            // 如果包含num - 1则说明已经计算过了，则直接跳过
            if (!set.contains(num - 1)) {
                int curNum = num;
                int curLength = 1;
                while (set.contains(curNum + 1)) {
                    curNum++;
                    curLength++;
                }
                longestLength = Math.max(longestLength, curLength);
            }
        }
        return longestLength;
    }

    @Test
    public void test() {
        System.out.println(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
    }

}
